class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        // 进阶解法: 贪心
        vector<int> ret;
        int n = nums.size();
        ret.push_back(nums[0]);
        for(int i = 1; i < n; i++)
        {
            if(nums[i] > ret.back())
                ret.push_back(nums[i]);
            else
            {
                // 二分查找
                int left = 0, right = ret.size() - 1;
                while(left < right)
                {
                    int mid = (left + right) >> 1;
                    if(ret[mid] < nums[i])
                        left = mid + 1;
                    else
                        right = mid;      
                }
                ret[left] = nums[i];
            }
        }
        return ret.size();
    }
};


// 以下是记忆化搜索的解法
// class Solution {
//     vector<int> memo;
//     int dfs(vector<int> &nums, int pos)
//     {
//         if(memo[pos] != -1)
//             return memo[pos];
//         int ret = 1;
//         for(int i = pos + 1; i < nums.size(); i++)
//             if(nums[i] > nums[pos])
//                 ret = max(ret, dfs(nums, i) + 1);
//         memo[pos] = ret;
//         return ret;
//     }
// public:
//     int lengthOfLIS(vector<int>& nums) {
//         int ret = 1;
//         memo = vector<int>(nums.size() + 1, -1);
//         // 最长递增子序列有可能是以任意位置开始的
//         for(int i = 0; i < nums.size(); i++)
//             ret = max(ret, dfs(nums, i));
//         return ret;
//     }
// };



